Mobile wireless ad-hoc networks consisting of thousands of mobile nodes are desirable for many applications. For example, the United States military has suggested utilizing a highly-adaptive “ultra-large” ad hoc network consisting of tens of thousands of nodes. Similarly, a large technology company has expressed interest in launching tens of thousands of networked balloons into the upper atmosphere in an effort to provide network access to users on the ground even in remote locations. Another example application may involve connecting thousands of in-flight commercial aircraft in the continental United States into a high-capacity airborne network. However, scaling ad-hoc networks to this size is difficult at best. In particular, efficient routing in such large dynamic networks is an open problem.